#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 50
void Get_next(int next[],int len,char *str)
{
    int i, j;
    i = 1;
    j = 0;
    next[0] = 0;
    while(i<len){
        if(str[i]==str[j]){
            next[i] = j + 1;
            i++;
            j++;
        }
        else{
            if(j==0)
            {
                next[i] = 0;
                i++;
            }
            else{
                j = next[j-1];
            }
        }
    }
}
int KMP(char *str1,int len1,char*str2,int len2)
{
    int next[MAXSIZE];
    Get_next(next,len2,str2);
    int i, j;
    i = j = 0;
    while (i<len1&&j<len2)
    {
        if(str1[i]==str2[j])
        {
            i++;
            j++;
        }
        else
        {
            if(j==0)
                i++;
            else
                j = next[j-1];       
        }
    }
    if(j == len2)
        return i - j;
    return -1;
}

int main()
{
    /*******************code*******************/
    char str1[] = {"abaabaabc"};
    char str2[] = {"abaabc"};
    int len1, len2;
    len1 = 9;
    len2 = 6;
    int p = KMP(str1,len1,str2,len2);
    printf("%d",p);
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
